When communications are conducted simultaneously among multiple nodes, a non-blocking network technology that ensures communication paths to cause no conflict among them has been used. Examples of such a technology include a non-blocking 3-stage Clos network, in which every communication between any pair of nodes is conducted through three intermediate transferring devices.
FIG. 18 is a diagram for explaining an example of the non-blocking 3-stage Clos network. A network 80 illustrated in FIG. 18 includes six nodes 81 to 86, switches 87 to 89 that serve as the first or third transferring devices, and crossbar switches (hereinafter, “XB's”) 90 to 92 that serve as the second transferring devices.
In the network 80, each of the switches 87 to 89 is mutually connected to each of the XB's 90 to 92, and each of the switches 87 to 89 is connected to two nodes. For the nodes, computers that form a cluster, network devices that are connected to an external network, or the likes are deployed.
To establish a new communication between a pair of nodes, the switches 87 to 89 of this network 80 execute a dynamic routing process including arbitration to select an XB that is not relaying any other communication to ensure that communication path do not cause conflict with others. More specifically, the switches 87 to 89 select an XB that is not used for any other communication either by a switch connected to the transmission node or by a switch connected to the reception node. Then, the switches 87 to 89 use the selected XB to relay the new communication between the nodes.
For example, when the node 81 and the node 86 are starting communications, the switch 87 searches for an XB that is not used for the communications either by itself or by the switch 89 connected to the node 86. When the XB 91 is not used for communication by either the switch 87 or the switch 89, the switch 87 selects the XB 91. Thereafter, the switch 87 uses the XB 91 to relay the communication between the node 81 and the node 86.
However, with the technology of connecting the switches and the XB to each other, when a new communication is to be established between some nodes, a dynamic routing process that involves arbitration is executed to avoid conflict among communication paths. As a result, when the delay allowed in communications between nodes is very short, overhead caused by the arbitration is not negligible.
This arbitration-related overhead may be reduced by reducing the number of nodes connected to each switch. However, to constitute a non-blocking network by reducing the number of nodes connected to each switch while maintaining the total number of nodes, it demands a large-scale XB to fully connect a large number of switches. An XB is usually realized by a large scale integrated circuit (LSI), and hence the XB needs a large number of pins to connect a large number of switches.
When a large-scale XB is not available, a non-blocking 3-stage Clos network may be deployed in place of an XB in the network. However, in such a network, a dynamic routing process that involves arbitration still has to be executed in the non-blocking 3-stage Clos network provided in place of the XB, and therefore overhead caused by the arbitration is not suppressed.
The technology disclosed herein resolves the problem of the dynamic routing process that involves arbitration, and reduces the arbitration-related overhead.